1. Field of the Invention
The invention relates generally to geometric modeling systems that, with the aid of a digital computer, may be used to capture, manipulate, analyze and report data. Examples of such systems include geographical positioning systems (GPS), geographic information systems (GIS), computer aided design (CAD) systems and computer aided manufacturing (CAM) systems. The invention also relates generally to communications networks, such as the public telephone network, local area networks (LANs), and the like, which include a set of nodes interconnected by a set of communication links (defining the network), used to transmit data between a start node and a target (destination) node.
More particularly, the invention relates to processes which enable the determination of the shortest path between two nodes in a network, or network represented in the modeling system, to be efficiently ascertained when compared with the known processes for making such determinations. The known processes can be time consuming to practice (from a processor utilization point of view), and have the potential for requiring relatively large amounts of storage. This is particularly true as the size of the network and number of possible paths between nodes increases. The processes contemplated by the invention enable the shortest path determination problem to be solved quickly and efficiently, even in very large networks having many possible paths between nodes, saving both time and the unnecessary use of computing resources.
2. Definitions
1. A "modeling system" is a system that may be used to process (capture and manipulate) real world data and events, and process abstract data based on real world data and events. Examples of modeling systems include, but are not limited to, geographical positioning systems (GPS), geographic information systems (GIS), computer aided design (CAD) systems and computer aided manufacturing (CAM) systems. PA1 2. A "modeling coordinate system" is a coordinate system which maps out a space that can completely contain all of the spatial or geometric data that a user can process using a given modeling system, in terms of a user's own units (e.g., feet, miles, degrees, etc.). PA1 3. A "database coordinate system" is a coordinate system that accommodates the storage of data from a users modeling coordinate system without the loss of accuracy. PA1 4. A "device coordinate system" is a coordinate system which maps out the available space on a given device (for example, a display device), into which data may be mapped. The data may, for example, be supplied via user interaction with a display device, may be mapped from (or to) a modeling coordinate system and/or database coordinate system, etc. PA1 5. A "linear network" whether a physical network or a network represented in a modeling system, is defined as a set of nodes interconnected via a set of weighted/directed edges (or links). PA1 6. A "permanent node" is defined as any given node in a linear network for which the shortest path from a designated start node to the given node has been fully determined. PA1 7. An array is defined as being "incrementally" created if a first portion of the array is constructed with direct reference to a given database, followed by a second portion of the array being constructed after further direct reference to the database, etc.; as opposed to an array that is constructed from a matrix or sparse matrix (itself constructed with reference to the database), without further reference to the database. PA1 8. An "array entry" is defined as a set of at least four array elements, including (a) an array element that uniquely identifies a given node in a linear network; (b) an array element that indicates if the given node is a permanent node; (c) an array element representing the calculated shortest weight to the given node, calculated as a function of the variable contents of array as the array is being constructed; and (4) an array element that indicates the identity of a previously visited node, in the path between the start node and the given node, which may be utilized to determine the shortest path from the target node back to the start node (at the completion of the array creation process), whenever the given node is actually in the shortest path between the start and target nodes. PA1 (a) providing the computer with a database that includes at least the first set of signals, wherein the database is accessible by the computer to retrieve data during the transformation process; and PA1 (b) incrementally creating an array of node identification signals with the aid of the computer, directly from the first set of signals provided to the computer via the database. PA1 1. The number of data queries needed (accesses to the given database in which a given network is defined), is reduced to a minimum. There is no need to query all of the data for the entire network. Only the minimal number of queries needed to successfully completed the type of processes contemplated by the invention are required. PA1 2. The amount of storage needed when tracing large networks (having several hundred, thousand or even greater numbers of nodes), is reduced by orders of magnitude since only a portion of the network is ever actually traced and needs to be stored. PA1 3. The time to complete the type of process contemplated by the invention is also significantly reduced since not every node in the network needs to be examined.